package UnionFind;

import java.util.*;

public class _721_AccountsMerge {
    /*
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> res = new ArrayList<>();
        List<Email> emails = new ArrayList<>();
        for (int i = 0; i < accounts.size(); i++) {
            List<String> account = accounts.get(i);
            boolean same = false;
            for (Email email : emails) {
                if (email.name .equals(account.get(0))) {
                    for (int j = 1; j <account.size(); j++) {
                        if (email.addrs.contains(account.get(j))) {
                            same = true;
                            email.add(account);
                            break;
                        }
                    }
                }
                if (same) {
                    break;
                }
            }
            if (!same) {
                Email email = new Email(account.get(0), account);
                emails.add(email);
            }
        }
        for (Email e : emails) {
            res.add(e.sort());
        }
        return res;
    }

     class Email {
        String name;
        Set<String> addrs;
        List<String> res;
        public Email(String name,List<String> addrs) {
            this.name = name;
            this.addrs = new HashSet<>();
            for (int i = 1; i < addrs.size(); i++) {
                this.addrs.add(addrs.get(i));
            }
        }

        public void add(List<String> addrs) {
            for (int i = 1; i < addrs.size(); i++) {
                this.addrs.add(addrs.get(i));
            }
        }

        public List<String> sort() {
            String[] addr = new String[addrs.size()];
            int i = 0;
            for (Iterator<String> it = addrs.iterator(); it.hasNext(); ) {
                addr[i++] = it.next();
            }
            Arrays.sort(addr);
            this.res = Arrays.asList(addr);
            List<String> ans = new ArrayList<>();
            ans.add(this.name);
            ans.addAll(this.res);
            return ans;
        }
    }*/
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> owner = new HashMap<>();
        Map<String, String> parents = new HashMap<>();
        Map<String, TreeSet<String>> unions = new HashMap<>();
        for (List<String> account : accounts) {
            int size = account.size();
            for (int i = 1; i < size; i++) {
                parents.put(account.get(i), account.get(i));
                owner.put(account.get(i), account.get(0));
            }
        }
        for (List<String> account : accounts) {
            int size = account.size();
            String p = find(account.get(1), parents);
            for (int i = 2; i < size; i++) {
                parents.put(find(account.get(i),parents), p);
            }
        }

        for (List<String> account : accounts) {
            int size = account.size();
            String p = find(account.get(1),parents);
            if (!unions.containsKey(p)) {
                unions.put(p, new TreeSet<>());
            }
            for (int i = 1; i <size ; i++) {
                unions.get(p).add(account.get(i));
            }
        }

        List<List<String>> res = new ArrayList<>();
        for (String p:unions.keySet()) {
            List<String> email = new ArrayList<>(unions.get(p));
            email.add(0, owner.get(p));
            res.add(email);
        }
        return res;
    }

    public String find(String s, Map<String, String> p) {
        return p.get(s).equals(s)? s : find(p.get(s), p);
    }

}